home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Loadstar 12
/
012.d81
/
lcm article
< prev
next >
Wrap
Text File
|
2022-08-26
|
2KB
|
125 lines
THE LCM OF TWO INTEGERS
DEFINITION: The LEAST COMMON MULTIPLE
(or LCM) of two integers, A and B, is
a positive integer M satisfying:
i) A divides M and B divides M.
ii) if M' is any other integer
such that A divides M' and B
divides M', then M' is also
divisible by M.
REMARK: The LCM of two positive
integers exists.
PROOF: The set of all positive
integers N such that A divides N,
and B divides N is not empty. (WHY?)
It is bounded below by 0. Therefore,
it must have a least element. We have
used the fact that the positive
integers are WELL ORDERED again.
If you couldn't answer the WHY? above,
set N=AB. Prove that both A and B
always divide AB.
THEOREM: Let A and B be two positive
integers, and let G be their GCD.
Then the LCM, M, of A and B is given
by
M = AB/G.
OUTLINE OF THE PROOF: First show that
A divides M and B divides M. ( This is
pretty easy. Use the fact that A/G
and B/G are integers.)
Then show that if M' is divisible by
both A and B, it must be divisible by
AB/G. That will show that AB/G is the
LCM of A and B. (HINT: write AB/G as
(A)(B/G) and use the following
result.)
LEMMA: If A, B, and C are positive
integers, such that A divides C and
B divides C, and if (A,B)=1, then
AB divides C.
PROOF OF LEMMA: Since (A,B)=1, there
exist integers D and E such that
(1) AD + BE = 1.
Then multiplying the above equation
by C,
(2) CAD + CBE = C.
Since A and B divide C, there exist
integers K and L such that
(3) C = KA and C = LB.
Substituting these values for C in the
left-hand side of equation (2),
(4) LBAD + KABE = C
Factoring AB from both terms on the
left,
(5) AB(LD + KE) = C.
Thus AB divides C.
REMARK: Notice that the fact that the
GCD of A and B being equal to 1 is
really necessary. As an example,
12 is divisible by 4 and 6, but 12 is
NOT divisible by (4)(6) = 24.
--------------------------------------